原帖地址：[http://blog.leanote.com/post/dawnmagnet/403](http://blog.leanote.c
om/post/dawnmagnet/403)
# 题目
![title](https://leanote.com/api/file/getImage?fileId=608a95a0ab6441531a006c0
1)
# 思路分析
这道题目是一个典型的游戏题，游戏一般来说做法就是（大家比较容易想到的）就是模
拟，而我们来看一下这个题目，是模拟青蛙跳。
主要的约束条件就是上一步和下一步的步长绝对值之间只能差1。很容易想到可以使用df
s做，那么我们来分析一下这个dfs需要使用几个参数。比较容易想到的是两个参数：一
个是上一步跳了k的长度，一个是上一步跳到的位置。这个是比较好想的。
但是对于这个题目，我们如果单纯的使用dfs一定会超时，因为如果我们剖析一下这个题
目，其实很像一个背包问题，就是从这么多石头里面选出来一条路径要经过的地方，然
后判断这个路径是否合法。而对于一个背包问题，dp无疑是更加快速和更好的解法，而d
fs和dp的联系也非常紧密，dfs的参数往往就可以作为dp数组的下标。甚至我们可以说，
dfs有两个参数，dp就应当是一个二维数组，他们之间存在一个一一对应的关系（对于记
忆化搜索而言）。对于dfs来说，dp无疑是一个更好的选择，因为它的抽象程度更高，也
不需要压很多递归的栈（每调用一个函数就会占用O(1)的栈空间），也减少了很多重复
计算，怎么都好，但同时抽象程度也变高了，对我们而言，提取题目信息的能力就尤为
重要。现在的重点变成了，如何在dp数组中模拟出来青蛙跳的逻辑。
多说不如实干，我们来模拟一下
## 模拟青蛙跳
模拟有从前向后和从后向前两种模式
dp[i][l]表示当前走到的最后一个节点是i号节点（不是i位置），最后一步的长度是l。
### 从前向后
假设我们已经知道了dp[i][l]，我们可以向后推演出dp[j][stones[j] - 
stones[i]]，前提是stones[j] - stones[i]和l,l+1和l-1其中的一个相等。
### 从后向前
假设我们还不知道dp[i][l]，我们可以用前面的数据向后推算。dp[i][l] = 
dp[j][k-1]||dp[j][k]||dp[j][k+1]，其中l=stones[j] - stones[i]
分析可以得出，从后向前比较简单易懂而且复杂度较低。
所以我们就采用该方法
### Rust代码
```rust
// dp[x][l] 跳到x，上一步长l
// dp[x][l] = dp[j][l-1]|dp[j][l]|dp[j][l+1]
impl Solution {
    pub fn can_cross(stones: Vec<i32>) -> bool {
        let n = stones.len();
        // for i in 1..n {
        //     if (stones[i] - stones[i - 1] > i as i32) {
        //         return false;
        //     }
        // }
        let mut dp = vec![vec![false; n]; n];
        dp[0][0] = true;
        for i in 1..n {
            for j in 0..i {
                let l = (stones[i] - stones[j]) as usize;
                if l > j + 1 {